package DoExercise.HSP_ZCY.A009_图结构.A001_并查集;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

/**
 * 从一个点出发，找出这个点到所有点的最短距离是多少？如果无法到达，距离就认为是无穷大
 * <p>
 * 迪杰斯特拉算法：求解单元点的最短路径问题：给定带权有向图G和源点v，求v到G中其他顶点的最短路径
 * 限制条件：图G中不存在负权值的边
 * <p>
 * 划重点，迪杰斯特拉最最朴素的思想就是按长度递增的次序产生最短路径。即每次对所有可见点的路径长度进行排序后，
 * 选择一条最短的路径，这条路径就是对应顶点到源点的最短路径。
 * <p>
 * 思路：
 * 1 从给定的某个点开始，确定该点到所有边的距离，找到最短的距离所到的点
 * 2 比较这个点当前计算的距离 是否小于 该点之前的权重 ，小就替换
 * 3 将该点加入到已处理集合，继续重复1-2过程
 */
public class Code06_迪杰斯特拉算法_D算法
{
    
    /**
     * 找到的每一个点到head的最短距离
     *
     * @param head
     * @return
     */
    public static HashMap<Node, Integer> dijkstra1(Node head)
    {
        HashMap<Node, Integer> distanceMap = new HashMap<>();//初始的记录表
        distanceMap.put(head, 0);
        HashSet<Node> selectedNodes = new HashSet<>();// 已经求过距离的节点，存在selectedNodes中，以后再也不碰
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null)
        {
            int distance = distanceMap.get(minNode);
            for (Edge edge : minNode.edges)//遍历最小点的所有边
            {
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode))//之前是无穷大
                {
                    distanceMap.put(toNode, distance + edge.weight);
                } else//之前有过记录
                {
                    distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
                }
            }
            selectedNodes.add(minNode);//锁住已经选择过的边
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);//继续在集合中找出距离最小的点，重复上述过程
        }
        return distanceMap;
    }
    
    /**
     * 从distanceMap中选出没在touchedNodes出现过的最小距离点
     *
     * @param distanceMap
     * @param touchedNodes
     * @return
     */
    public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes)
    {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Entry<Node, Integer> entry : distanceMap.entrySet())
        {
            Node node = entry.getKey();
            int distance = entry.getValue();
            if (!touchedNodes.contains(node) && distance < minDistance)
            {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }
    
    /**
     * 上面的方法需要遍历Map所以产生下面的方法，时间复杂度o(N)，使用小根堆提高效率，o(LogN)
     */
    
    public static class NodeRecord
    {
        public Node node;//当前节点
        public int distance;//最小距离
        
        public NodeRecord(Node node, int distance)
        {
            this.node = node;
            this.distance = distance;
        }
    }
    
    /**
     * 根据特点需求改写堆
     */
    public static class NodeHeap
    {
        private Node[] nodes; // 实际的堆结构
        // key 某一个node， value 上面堆中的位置。如果是-1表示之前在，现在不在
        private HashMap<Node, Integer> heapIndexMap;
        // key 某一个节点， value 从原节点出发到该节点的目前最小距离
        private HashMap<Node, Integer> distanceMap;
        private int size; // 堆上有多少个点
        
        public NodeHeap(int size)
        {
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            size = 0;
        }
        
        public boolean isEmpty()
        {
            return size == 0;
        }
        
        // 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
        // 判断要不要更新，如果需要的话，就更新
        public void addOrUpdateOrIgnore(Node node, int distance)
        {
            if (inHeap(node))
            {
                distanceMap.put(node, Math.min(distanceMap.get(node), distance));
                insertHeapify(heapIndexMap.get(node));//从当前节点开始重新堆化
            }
            if (!isEntered(node))//新记录
            {
                nodes[size] = node;
                heapIndexMap.put(node, size);
                distanceMap.put(node, distance);
                insertHeapify(size++);
            }
            //其他情况就是-1
        }
        
        public NodeRecord pop()
        {
            NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
            swap(0, size - 1);
            heapIndexMap.put(nodes[size - 1], -1);
            distanceMap.remove(nodes[size - 1]);
            // free C++同学还要把原本堆顶节点析构，对java同学不必
            nodes[size - 1] = null;
            heapify(0, --size);
            return nodeRecord;
        }
        
        /**
         * 堆排序的移动
         *
         * @param index
         */
        private void insertHeapify(int index)
        {
            //当前节点距离比父亲节点小，则当前节点和父亲节点交换
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2]))
            {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }
        
        private void heapify(int index, int size)
        {
            int left = index * 2 + 1;
            while (left < size)
            {
                //左右两个节点谁小
                int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left]) ? left + 1 : left;
                //小的和父节点比较，得到最小的节点
                smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
                if (smallest == index) break;
                swap(smallest, index);
                index = smallest;
                left = index * 2 + 1;
            }
        }
        
        /**
         * 某个节点是否进入过堆，-1也是进入
         *
         * @param node
         * @return
         */
        private boolean isEntered(Node node)
        {
            return heapIndexMap.containsKey(node);
        }
        
        /**
         * 某点在堆中，且不是-1，表明该点在堆中
         *
         * @param node
         * @return
         */
        private boolean inHeap(Node node)
        {
            return isEntered(node) && heapIndexMap.get(node) != -1;
        }
        
        private void swap(int index1, int index2)
        {
            heapIndexMap.put(nodes[index1], index2);
            heapIndexMap.put(nodes[index2], index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }
    }
    
    
    /**
     * 改进后的dijkstra算法
     * 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
     *
     * @param head
     * @param size
     * @return
     */
    public static HashMap<Node, Integer> dijkstra2(Node head, int size)
    {
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrIgnore(head, 0);
        HashMap<Node, Integer> result = new HashMap<>();
        while (!nodeHeap.isEmpty())
        {
            NodeRecord record = nodeHeap.pop();
            Node cur = record.node;
            int distance = record.distance;
            for (Edge edge : cur.edges)
            {
                nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
            }
            result.put(cur, distance);//锁定
        }
        return result;
    }
    
}
